#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//#define SWAP(X, Y)  {X ^= Y; Y ^= X; X ^= Y;}
void Swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;   
    *b = tmp;    
}

int Partition(int *a, int p, int r)
{
    int x = a[r];
    int i = p - 1;
    int j = p;
    
    for (; j <= (r - 1); j++)
        if (a[j] < x)
        {
            i++;
            Swap(&a[i], &a[j]);
        }
    Swap(&a[i+1], &a[r]);
    return i+1;
}

int RandomPartition(int *a, int p, int r)
{
    srand((unsigned)time(0));
    int i;
    i = (rand() % (r - p)) + p;
    
    Swap(&a[i], &a[r]);
    return Partition(a, p, r);
}

int RandomSelect(int *a, int p, int r, int i)
{
    int q;
    int k;
    
    if (p == r)
        return a[p];            /* there is only one element. */
    q = RandomPartition(a, p, r);
    k = q - p + 1;
    if (i == k)                 /* the pivot value is answer. */
        return a[q];
    else if (i < k)
        return RandomSelect(a, p, q - 1, i);
    else
        return RandomSelect(a, q+1, r, i - k);
}

int main(int argc, char *argv[])
{
    int a[8] = {2, 3, 5, 7, 8, 1, 0, 9};
    
    printf("%d\n",RandomSelect(a, 0, 7, 8));
    
    return 0;
}
